package liurong.driver.leet;

import java.util.Arrays;

/**
 * 
 * @desc 贪心算法
 *
 * @author liurong
 *
 * @date 2020年6月24日
 */
public class LeetCode455Test {

	public static void main(String[] args) {
		int[] g = { 10, 9, 8, 7 };
		int[] s = { 5, 6, 7, 8 };
		System.out.println(findContentChildren(g, s));
		System.out.println(findContentChildrenV2(g, s));
	}

	/**
	 * s[i] >= g[j]
	 * 
	 * @param g 孩子们的胃口
	 * @param s 饼干
	 * @return
	 */
	public static int findContentChildren(int[] g, int[] s) {
		Arrays.sort(g);
		Arrays.sort(s);
		int count = 0;
		int gIndex = 0;// 代表饼干的位置
		int forcount = 0;
		for (int si : s) {
			for (int j = gIndex; j < g.length; j++) {
				forcount++;
				if (si >= g[j]) {
					count++;
					if (gIndex == g.length) {
						System.out.println(forcount);
						return count;
					}
					gIndex = ++j;
					break;
				}
			}
		}

		System.out.println(forcount);
		return count;
	}

	/**
	 * s[i] >= g[j]
	 * 
	 * @param g 孩子们的胃口
	 * @param s 饼干
	 * @return
	 */
	public static int findContentChildrenV2(int[] g, int[] s) {
		Arrays.sort(g);
		Arrays.sort(s);

		int child = 0;
		int cookie = 0;

		while (child < g.length && cookie < s.length) {
			if (s[cookie] >= g[child]) {
				child++;
			}
			cookie++;
		}

		return child;
	}
}
